<!DOCTYPE html>
<html lang="zh-CN,en,zh-TW,default">
  <head hexo-theme='https://github.com/volantis-x/hexo-theme-volantis/tree/4.2.0'>
  <meta charset="utf-8">
  <!-- SEO相关 -->
  
    
  
  <!-- 渲染优化 -->
  <meta http-equiv='x-dns-prefetch-control' content='on' />
  <link rel='dns-prefetch' href='https://cdn.jsdelivr.net'>
  <link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin>
  <meta name="renderer" content="webkit">
  <meta name="force-rendering" content="webkit">
  <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
  <meta name="HandheldFriendly" content="True" >
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

  <!-- 页面元数据 -->
  
  <title>Arrays.sort()源码解读+流程图总结 - Yayako&#39;s Blog</title>
  
    <meta name="keywords" content="Java,源码">
  

  
    <meta name="description" content="Java中Arrays.sort()源码的跟踪注释，重点在归并排序和快速排序两点，最后画了流程图做总结。">
  

  <!-- feed -->
  

  <!-- import meta -->
  

  <!-- link -->
  
    <link rel="shortcut icon" type='image/x-icon' href="https://halo-yayako.oss-cn-hangzhou.aliyuncs.com/icons8-lamb-96_1600147384617.png">
  

  <!-- import link -->
  

  
    
<link rel="stylesheet" href="/css/first.css">

  

  
  <link rel="stylesheet" href="/css/style.css" media="print" onload="this.media='all';this.onload=null">
  <noscript><link rel="stylesheet" href="/css/style.css"></noscript>
  

  <script id="loadcss"></script>

  

<script>if (/*@cc_on!@*/false || (!!window.MSInputMethodContext && !!document.documentMode)) document.write('\x3Cscript id="_iealwn_js" data-outver="11" src="https://support.dmeng.net/ie-alert-warning/latest.js">\x3C/script>'); </script>

</head>

  <body>
    

<header id="l_header" class="l_header always shadow blur "  >
  <div class='container'>
  <div id='wrapper'>
    <div class='nav-sub'>
      <p class="title"></p>
      <ul class='switcher nav-list-h m-phone' id="pjax-header-nav-list">
        <li><a id="s-comment" class="fas fa-comments fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
          <li><a id="s-toc" class="s-toc fas fa-list fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
      </ul>
    </div>
		<div class="nav-main">
      
        
        <a class="title flat-box" target="_self" href='/'>
          
            <img no-lazy class='logo' src='https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/icons8-doughnut-100.png'/>
          
          
          
        </a>
      

			<div class='menu navigation'>
				<ul class='nav-list-h m-pc'>
          
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/
                  
                  
                  
                    id="categoriesJava"
                  >
                  Java
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesJavaE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/JVM/
                  
                  
                  
                    id="categoriesJavaJVM"
                  >
                  JVM
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/J.U.C/
                  
                  
                  
                    id="categoriesJavaJUC"
                  >
                  J.U.C
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/
                  
                  
                  
                    id="categoriesGolang"
                  >
                  Golang
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/%E5%9F%BA%E7%A1%80
                  
                  
                  
                    id="categoriesGolangE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/
                  
                  
                  
                    id="categoriesE6A186E69EB6"
                  >
                  框架
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/SSM/
                  
                  
                  
                    id="categoriesE6A186E69EB6SSM"
                  >
                  SSM
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6"
                  >
                  中间件
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/Redis/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6Redis"
                  >
                  Redis
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/
                  
                  
                  
                    id="categoriesMySQL"
                  >
                  MySQL
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesMySQLE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/InnoDB/
                  
                  
                  
                    id="categoriesMySQLInnoDB"
                  >
                  InnoDB
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/
                  
                  
                  
                    id="categoriesE7AE97E6B395"
                  >
                  算法
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/LeetCode/
                  
                  
                  
                    id="categoriesE7AE97E6B395LeetCode"
                  >
                  LeetCode
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/%E5%89%91%E6%8C%87offer/
                  
                  
                  
                    id="categoriesE7AE97E6B395E58991E68C87offer"
                  >
                  剑指offer
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/
                  
                  
                  
                    id="categoriesE5B7A5E585B7"
                  >
                  工具
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Linux/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Linux"
                  >
                  Linux
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Nginx/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Nginx"
                  >
                  Nginx
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Docker/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Docker"
                  >
                  Docker
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/
                  
                  
                  
                    id="categoriesE585B6E4BB96"
                  >
                  其他
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/%E9%9D%A2%E7%BB%8F/
                  
                  
                  
                    id="categoriesE585B6E4BB96E99DA2E7BB8F"
                  >
                  面经
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
				</ul>
			</div>

      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <i class="icon fas fa-search fa-fw"></i>
          <input type="text" class="input u-search-input" placeholder="Search..." />
        </form>
      </div>

			<ul class='switcher nav-list-h m-phone'>
				
					<li><a class="s-search fas fa-search fa-fw" target="_self" href='javascript:void(0)'></a></li>
				
				<li>
          <a class="s-menu fas fa-bars fa-fw" target="_self" href='javascript:void(0)'></a>
          <ul class="menu-phone list-v navigation white-box">
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/
                  
                  
                  
                    id="categoriesJava"
                  >
                  Java
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesJavaE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/JVM/
                  
                  
                  
                    id="categoriesJavaJVM"
                  >
                  JVM
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/J.U.C/
                  
                  
                  
                    id="categoriesJavaJUC"
                  >
                  J.U.C
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/
                  
                  
                  
                    id="categoriesGolang"
                  >
                  Golang
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/%E5%9F%BA%E7%A1%80
                  
                  
                  
                    id="categoriesGolangE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/
                  
                  
                  
                    id="categoriesE6A186E69EB6"
                  >
                  框架
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/SSM/
                  
                  
                  
                    id="categoriesE6A186E69EB6SSM"
                  >
                  SSM
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6"
                  >
                  中间件
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/Redis/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6Redis"
                  >
                  Redis
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/
                  
                  
                  
                    id="categoriesMySQL"
                  >
                  MySQL
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesMySQLE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/InnoDB/
                  
                  
                  
                    id="categoriesMySQLInnoDB"
                  >
                  InnoDB
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/
                  
                  
                  
                    id="categoriesE7AE97E6B395"
                  >
                  算法
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/LeetCode/
                  
                  
                  
                    id="categoriesE7AE97E6B395LeetCode"
                  >
                  LeetCode
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/%E5%89%91%E6%8C%87offer/
                  
                  
                  
                    id="categoriesE7AE97E6B395E58991E68C87offer"
                  >
                  剑指offer
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/
                  
                  
                  
                    id="categoriesE5B7A5E585B7"
                  >
                  工具
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Linux/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Linux"
                  >
                  Linux
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Nginx/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Nginx"
                  >
                  Nginx
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Docker/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Docker"
                  >
                  Docker
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/
                  
                  
                  
                    id="categoriesE585B6E4BB96"
                  >
                  其他
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/%E9%9D%A2%E7%BB%8F/
                  
                  
                  
                    id="categoriesE585B6E4BB96E99DA2E7BB8F"
                  >
                  面经
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
          </ul>
        </li>
			</ul>
		</div>
	</div>
  </div>
</header>

    <div id="l_body">
      <div id="l_cover">
  
    
        <div id="half" class='cover-wrapper post search' style="display: ;">
          
            <div id='cover-backstretch'></div>
          
          <div class='cover-body'>
  <div class='top'>
    
    
      <p class="title">Yayako's Blog</p>
    
    
      <p class="subtitle">「Shooting for the stars when I couldn't make a killing.」</p>
    
  </div>
  <div class='bottom'>
    
      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <input type="text" class="input u-search-input" placeholder="Have a nice day!" />
          <i class="icon fas fa-search fa-fw"></i>
        </form>
      </div>
    
    <div class='menu navigation'>
      <div class='list-h'>
        
          
            <a href="/"
              
              
              id="home">
              <i class='fas fa-home fa-fw'></i><p>首页</p>
            </a>
          
            <a href="/categories/"
              
              
              id="categories">
              <i class='fas fa-folder-open fa-fw'></i><p>分类</p>
            </a>
          
            <a href="/archives/"
              
              
              id="archives">
              <i class='fas fa-archive fa-fw'></i><p>归档</p>
            </a>
          
            <a href="/tags/"
              
              
              id="tags">
              <i class='fas fa-tags fa-fw'></i><p>标签</p>
            </a>
          
            <a href="/friends/"
              
              
              id="friends">
              <i class='fas fa-link fa-fw'></i><p>友链</p>
            </a>
          
            <a href="/about/"
              
              
              id="about">
              <i class='fas fa-user fa-fw'></i><p>关于</p>
            </a>
          
        
      </div>
    </div>
  </div>
</div>

          <div id="scroll-down" style="display: none;"><i class="fa fa-chevron-down scroll-down-effects"></i></div>
        </div>
    
  
  </div>

      <div id="safearea">
        <div class="body-wrapper" id="pjax-container">
          

<div class='l_main'>
  <article class="article post white-box reveal md shadow article-type-post" id="post" itemscope itemprop="blogPost">
  


  
  <div class="article-meta" id="top">
    
    
    
      <h1 class="title">
        Arrays.sort()源码解读+流程图总结
      </h1>
      <div class='new-meta-box'>
        
          
            
<div class='new-meta-item author'>
  <a class='author' href="/about" rel="nofollow">
    <img no-lazy src="https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/icons8-cat-100%20%282%29.png">
    <p>yayako</p>
  </a>
</div>

          
        
          
            <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt fa-fw" aria-hidden="true"></i>
    <p>发布于：2020年1月22日</p>
  </a>
</div>

          
        
          
            
  <div class="new-meta-item browse leancloud">
    <a class='notlink'>
      
      <div id="lc-pv" data-title="Arrays.sort()源码解读+流程图总结" data-path="/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/">
        <i class="fas fa-eye fa-fw" aria-hidden="true"></i>
        <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span>
        次浏览
      </div>
    </a>
  </div>


          
        
          
            
<div class="new-meta-item comments-count">
  
  <a href="/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/#comments">
    <i class="fas fa-comment-dots fa-fw"></i>
    <span class="valine-comment-count" data-xid="/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/">0</span>
    <span class="leancloud-comments-count">&nbsp;条评论</span>
  </a>
</div>


          
        
      </div>
    
  </div>


  
  
  <h2 id="Arrays-sort"><a href="#Arrays-sort" class="headerlink" title="Arrays.sort()"></a>Arrays.sort()</h2><blockquote>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">public static void sort(int[] a)</span><br></pre></td></tr></table></figure>

<p>Sorts the specified array into ascending numerical order.</p>
<p>将指定数组按升序排序。</p>
<p>Implementation note: The sorting algorithm is a <strong>Dual-Pivot Quicksort</strong> by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers <strong>O(n log(n))</strong> performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.</p>
<p>双轴快排，在许多数据集上的时间复杂度实现在 O(n log(n))，导致其他快排的性能降级。比传统快排更快。</p>
<ul>
<li><p><strong>Parameters:</strong></p>
<p><code>a</code> - the array to be sorted</p>
</li>
</ul>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] a)</span> </span>&#123;</span><br><span class="line">    DualPivotQuicksort.sort(a, <span class="number">0</span>, a.length - <span class="number">1</span>, <span class="keyword">null</span>, <span class="number">0</span>, <span class="number">0</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="DualPivotQuicksort-sort"><a href="#DualPivotQuicksort-sort" class="headerlink" title="DualPivotQuicksort.sort()"></a>DualPivotQuicksort.sort()</h2><h3 id="归并部分"><a href="#归并部分" class="headerlink" title="归并部分"></a>归并部分</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * If the length of an array to be sorted is less than this</span></span><br><span class="line"><span class="comment"> * constant, Quicksort is used in preference to merge sort.</span></span><br><span class="line"><span class="comment"> * 快排阈值。排序数组的长度小于286，使用快排。</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> QUICKSORT_THRESHOLD = <span class="number">286</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * The maximum number of runs in merge sort.</span></span><br><span class="line"><span class="comment"> * 归并排序阈值。</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAX_RUN_COUNT = <span class="number">67</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] a, <span class="keyword">int</span> left, <span class="keyword">int</span> right, <span class="keyword">int</span>[] work, <span class="keyword">int</span> workBase, <span class="keyword">int</span> workLen)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// Use Quicksort on small arrays</span></span><br><span class="line">    <span class="comment">// 数组长度小于快排阈值，使用快排。</span></span><br><span class="line">    <span class="keyword">if</span> (right - left &lt; QUICKSORT_THRESHOLD) &#123;</span><br><span class="line">        sort(a, left, right, <span class="keyword">true</span>);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * Index run[i] is the start of i-th run</span></span><br><span class="line"><span class="comment">     * (ascending or descending sequence).</span></span><br><span class="line"><span class="comment">     * run数组用于记录部分有序数组块的边界索引，一定程度上说明了该排序对象的结构化程度（run数组使用的越多，说明该数组越乱，反之说明该数组富有结构化，存在大部分连续的有序部分）</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">int</span>[] run = <span class="keyword">new</span> <span class="keyword">int</span>[MAX_RUN_COUNT + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line">    run[<span class="number">0</span>] = left;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Check if the array is nearly sorted</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> k = left; k &lt; right; run[count] = k) &#123;</span><br><span class="line">        <span class="keyword">if</span> (a[k] &lt; a[k + <span class="number">1</span>]) &#123; <span class="comment">// ascending</span></span><br><span class="line">            <span class="comment">// 顺序，跳过</span></span><br><span class="line">            <span class="keyword">while</span> (++k &lt;= right &amp;&amp; a[k - <span class="number">1</span>] &lt;= a[k]) ;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (a[k] &gt; a[k + <span class="number">1</span>]) &#123; <span class="comment">// descending</span></span><br><span class="line">            <span class="comment">// 倒序</span></span><br><span class="line">            <span class="keyword">while</span> (++k &lt;= right &amp;&amp; a[k - <span class="number">1</span>] &gt;= a[k]) ;</span><br><span class="line">            <span class="comment">// 将倒序部分顺序排列</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> lo = run[count] - <span class="number">1</span>, hi = k; ++lo &lt; --hi; ) &#123;</span><br><span class="line">                <span class="keyword">int</span> t = a[lo];</span><br><span class="line">                a[lo] = a[hi];</span><br><span class="line">                a[hi] = t;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123; <span class="comment">// equal</span></span><br><span class="line">            <span class="comment">// 有MAX_RUN_LENGTH（33）个连续相同的元素，使用快排</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> m = MAX_RUN_LENGTH; ++k &lt;= right &amp;&amp; a[k - <span class="number">1</span>] == a[k]; ) &#123;</span><br><span class="line">                <span class="keyword">if</span> (--m == <span class="number">0</span>) &#123;</span><br><span class="line">                    sort(a, left, right, <span class="keyword">true</span>);</span><br><span class="line">                    <span class="keyword">return</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">         * The array is not highly structured,</span></span><br><span class="line"><span class="comment">         * use Quicksort instead of merge sort.</span></span><br><span class="line"><span class="comment">         * 数组结构话程度不高（非常乱序，时高时低），使用快排</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="keyword">if</span> (++count == MAX_RUN_COUNT) &#123;</span><br><span class="line">            sort(a, left, right, <span class="keyword">true</span>);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Check special cases</span></span><br><span class="line">    <span class="comment">// Implementation note: variable &quot;right&quot; is increased by 1.</span></span><br><span class="line">    <span class="keyword">if</span> (run[count] == right++) &#123; <span class="comment">// The last run contains one element</span></span><br><span class="line">        run[++count] = right;</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (count == <span class="number">1</span>) &#123; <span class="comment">// The array is already sorted</span></span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Determine alternation base for merge</span></span><br><span class="line">    <span class="keyword">byte</span> odd = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> n = <span class="number">1</span>; (n &lt;&lt;= <span class="number">1</span>) &lt; count; odd ^= <span class="number">1</span>) ;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Use or create temporary array b for merging</span></span><br><span class="line">    <span class="keyword">int</span>[] b; <span class="comment">// temp array; alternates with a</span></span><br><span class="line">    <span class="keyword">int</span> ao, bo; <span class="comment">// array offsets from &#x27;left&#x27;</span></span><br><span class="line">    <span class="keyword">int</span> blen = right - left; <span class="comment">// space needed for b</span></span><br><span class="line">    <span class="keyword">if</span> (work == <span class="keyword">null</span> || workLen &lt; blen || workBase + blen &gt; work.length) &#123;</span><br><span class="line">        work = <span class="keyword">new</span> <span class="keyword">int</span>[blen];</span><br><span class="line">        workBase = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (odd == <span class="number">0</span>) &#123;</span><br><span class="line">        System.arraycopy(a, left, work, workBase, blen);</span><br><span class="line">        b = a;</span><br><span class="line">        bo = <span class="number">0</span>;</span><br><span class="line">        a = work;</span><br><span class="line">        ao = workBase - left;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        b = work;</span><br><span class="line">        ao = <span class="number">0</span>;</span><br><span class="line">        bo = workBase - left;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Merging</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> last; count &gt; <span class="number">1</span>; count = last) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> k = (last = <span class="number">0</span>) + <span class="number">2</span>; k &lt;= count; k += <span class="number">2</span>) &#123;</span><br><span class="line">            <span class="keyword">int</span> hi = run[k], mi = run[k - <span class="number">1</span>];</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = run[k - <span class="number">2</span>], p = i, q = mi; i &lt; hi; ++i) &#123;</span><br><span class="line">                <span class="keyword">if</span> (q &gt;= hi || p &lt; mi &amp;&amp; a[p + ao] &lt;= a[q + ao]) &#123;</span><br><span class="line">                    b[i + bo] = a[p++ + ao];</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    b[i + bo] = a[q++ + ao];</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            run[++last] = hi;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> ((count &amp; <span class="number">1</span>) != <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = right, lo = run[count - <span class="number">1</span>]; --i &gt;= lo; b[i + bo] = a[i + ao]) ;</span><br><span class="line">            run[++last] = right;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span>[] t = a;</span><br><span class="line">        a = b;</span><br><span class="line">        b = t;</span><br><span class="line">        <span class="keyword">int</span> o = ao;</span><br><span class="line">        ao = bo;</span><br><span class="line">        bo = o;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="快排部分"><a href="#快排部分" class="headerlink" title="快排部分"></a>快排部分</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br><span class="line">307</span><br><span class="line">308</span><br><span class="line">309</span><br><span class="line">310</span><br><span class="line">311</span><br><span class="line">312</span><br><span class="line">313</span><br><span class="line">314</span><br><span class="line">315</span><br><span class="line">316</span><br><span class="line">317</span><br><span class="line">318</span><br><span class="line">319</span><br><span class="line">320</span><br><span class="line">321</span><br><span class="line">322</span><br><span class="line">323</span><br><span class="line">324</span><br><span class="line">325</span><br><span class="line">326</span><br><span class="line">327</span><br><span class="line">328</span><br><span class="line">329</span><br><span class="line">330</span><br><span class="line">331</span><br><span class="line">332</span><br><span class="line">333</span><br><span class="line">334</span><br><span class="line">335</span><br><span class="line">336</span><br><span class="line">337</span><br><span class="line">338</span><br><span class="line">339</span><br><span class="line">340</span><br><span class="line">341</span><br><span class="line">342</span><br><span class="line">343</span><br><span class="line">344</span><br><span class="line">345</span><br><span class="line">346</span><br><span class="line">347</span><br><span class="line">348</span><br><span class="line">349</span><br><span class="line">350</span><br><span class="line">351</span><br><span class="line">352</span><br><span class="line">353</span><br><span class="line">354</span><br><span class="line">355</span><br><span class="line">356</span><br><span class="line">357</span><br><span class="line">358</span><br><span class="line">359</span><br><span class="line">360</span><br><span class="line">361</span><br><span class="line">362</span><br><span class="line">363</span><br><span class="line">364</span><br><span class="line">365</span><br><span class="line">366</span><br><span class="line">367</span><br><span class="line">368</span><br><span class="line">369</span><br><span class="line">370</span><br><span class="line">371</span><br><span class="line">372</span><br><span class="line">373</span><br><span class="line">374</span><br><span class="line">375</span><br><span class="line">376</span><br><span class="line">377</span><br><span class="line">378</span><br><span class="line">379</span><br><span class="line">380</span><br><span class="line">381</span><br><span class="line">382</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * If the length of an array to be sorted is less than this</span></span><br><span class="line"><span class="comment"> * constant, insertion sort is used in preference to Quicksort.</span></span><br><span class="line"><span class="comment"> * 插入排序阈值。</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> INSERTION_SORT_THRESHOLD = <span class="number">47</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Sorts the specified range of the array by Dual-Pivot Quicksort.</span></span><br><span class="line"><span class="comment"> * 使用双轴快排对数组进行排序。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> a the array to be sorted</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> left the index of the first element, inclusive, to be sorted</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> right the index of the last element, inclusive, to be sorted</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> leftmost indicates if this part is the leftmost in the range 表示该部分数组是否在原数组的最左侧</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">sort</span><span class="params">(<span class="keyword">int</span>[] a, <span class="keyword">int</span> left, <span class="keyword">int</span> right, <span class="keyword">boolean</span> leftmost)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = right - left + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Use insertion sort on tiny arrays</span></span><br><span class="line">    <span class="comment">// 在小型数组上使用插入排序</span></span><br><span class="line">    <span class="keyword">if</span> (length &lt; INSERTION_SORT_THRESHOLD) &#123;</span><br><span class="line">        <span class="comment">// 需要排序部分的数组在原数组最左侧</span></span><br><span class="line">	    <span class="keyword">if</span> (leftmost) &#123;</span><br><span class="line">		    <span class="comment">/*</span></span><br><span class="line"><span class="comment">		     * Traditional (without sentinel) insertion sort,</span></span><br><span class="line"><span class="comment">		     * optimized for server VM, is used in case of</span></span><br><span class="line"><span class="comment">		     * the leftmost part.</span></span><br><span class="line"><span class="comment">		     * 最左侧数组使用针对服务器环境优化的传统（没有使用哨兵）的插入排序。</span></span><br><span class="line"><span class="comment">		     */</span></span><br><span class="line">		    <span class="keyword">for</span> (<span class="keyword">int</span> i = left, j = i; i &lt; right; j = ++i) &#123;</span><br><span class="line">			    <span class="keyword">int</span> ai = a[i + <span class="number">1</span>];</span><br><span class="line">			    <span class="keyword">while</span> (ai &lt; a[j]) &#123;</span><br><span class="line">				    a[j + <span class="number">1</span>] = a[j];</span><br><span class="line">				    <span class="keyword">if</span> (j-- == left) &#123;</span><br><span class="line">					    <span class="keyword">break</span>;</span><br><span class="line">				    &#125;</span><br><span class="line">			    &#125;</span><br><span class="line">			    a[j + <span class="number">1</span>] = ai;</span><br><span class="line">		    &#125;</span><br><span class="line">        <span class="comment">// 非最左侧</span></span><br><span class="line">	    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">		    <span class="comment">/*</span></span><br><span class="line"><span class="comment">		     * Skip the longest ascending sequence.</span></span><br><span class="line"><span class="comment">		     * 跳过升序部分</span></span><br><span class="line"><span class="comment">		     */</span></span><br><span class="line">		    <span class="keyword">do</span> &#123;</span><br><span class="line">			    <span class="keyword">if</span> (left &gt;= right) &#123;</span><br><span class="line">				    <span class="keyword">return</span>;</span><br><span class="line">			    &#125;</span><br><span class="line">		    &#125; <span class="keyword">while</span> (a[++left] &gt;= a[left - <span class="number">1</span>]);</span><br><span class="line"></span><br><span class="line">		    <span class="comment">/*</span></span><br><span class="line"><span class="comment">		     * Every element from adjoining part plays the role</span></span><br><span class="line"><span class="comment">		     * of sentinel, therefore this allows us to avoid the</span></span><br><span class="line"><span class="comment">		     * left range check on each iteration. Moreover, we use</span></span><br><span class="line"><span class="comment">		     * the more optimized algorithm, so called pair insertion</span></span><br><span class="line"><span class="comment">		     * sort, which is faster (in the context of Quicksort)</span></span><br><span class="line"><span class="comment">		     * than traditional implementation of insertion sort.</span></span><br><span class="line"><span class="comment">		     * 相邻部分中的每个元素都起着哨兵的作用，这使得我们可以不用每次迭代都</span></span><br><span class="line"><span class="comment">		     * 去检查左边的边界。并使用了pair insertion sort（分组插入排序）</span></span><br><span class="line"><span class="comment">		     * 做优化（比传统的插入排序更快）。</span></span><br><span class="line"><span class="comment">		     */</span></span><br><span class="line">		    <span class="keyword">for</span> (<span class="keyword">int</span> k = left; ++left &lt;= right; k = ++left) &#123;</span><br><span class="line">			    <span class="keyword">int</span> a1 = a[k], a2 = a[left];</span><br><span class="line"></span><br><span class="line">			    <span class="keyword">if</span> (a1 &lt; a2) &#123;</span><br><span class="line">				    a2 = a1; a1 = a[left];</span><br><span class="line">			    &#125;</span><br><span class="line">			    <span class="keyword">while</span> (a1 &lt; a[--k]) &#123;</span><br><span class="line">				    a[k + <span class="number">2</span>] = a[k];</span><br><span class="line">			    &#125;</span><br><span class="line">			    a[++k + <span class="number">1</span>] = a1;</span><br><span class="line"></span><br><span class="line">			    <span class="keyword">while</span> (a2 &lt; a[--k]) &#123;</span><br><span class="line">				    a[k + <span class="number">1</span>] = a[k];</span><br><span class="line">			    &#125;</span><br><span class="line">			    a[k + <span class="number">1</span>] = a2;</span><br><span class="line">		    &#125;</span><br><span class="line">		    <span class="keyword">int</span> last = a[right];</span><br><span class="line"></span><br><span class="line">		    <span class="keyword">while</span> (last &lt; a[--right]) &#123;</span><br><span class="line">			    a[right + <span class="number">1</span>] = a[right];</span><br><span class="line">		    &#125;</span><br><span class="line">		    a[right + <span class="number">1</span>] = last;</span><br><span class="line">	    &#125;</span><br><span class="line">	    <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Inexpensive approximation of length / 7</span></span><br><span class="line">    <span class="comment">// 取七分之一的长度（这个位运算真令人折服）</span></span><br><span class="line">    <span class="keyword">int</span> seventh = (length &gt;&gt; <span class="number">3</span>) + (length &gt;&gt; <span class="number">6</span>) + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * Sort five evenly spaced elements around (and including) the</span></span><br><span class="line"><span class="comment">     * center element in the range. These elements will be used for</span></span><br><span class="line"><span class="comment">     * pivot selection as described below. The choice for spacing</span></span><br><span class="line"><span class="comment">     * these elements was empirically determined to work well on</span></span><br><span class="line"><span class="comment">     * a wide variety of inputs.</span></span><br><span class="line"><span class="comment">     * 在该范围中的中心元素周围（包括中心元素）将五个均匀分布的元素块进行排序。</span></span><br><span class="line"><span class="comment">     * 这些元素会被用作下面提到的枢轴。分割元素块的选择是基于经验确定的，</span></span><br><span class="line"><span class="comment">     * 可以很好地应用在多种输入上。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="comment">// 得到五个分割点</span></span><br><span class="line">    <span class="keyword">int</span> e3 = (left + right) &gt;&gt;&gt; <span class="number">1</span>; <span class="comment">// The midpoint</span></span><br><span class="line">    <span class="keyword">int</span> e2 = e3 - seventh;</span><br><span class="line">    <span class="keyword">int</span> e1 = e2 - seventh;</span><br><span class="line">    <span class="keyword">int</span> e4 = e3 + seventh;</span><br><span class="line">    <span class="keyword">int</span> e5 = e4 + seventh;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Sort these elements using insertion sort</span></span><br><span class="line">    <span class="comment">// 使用插入排序先将这些分割点相对排序</span></span><br><span class="line">    <span class="keyword">if</span> (a[e2] &lt; a[e1]) &#123; <span class="keyword">int</span> t = a[e2]; a[e2] = a[e1]; a[e1] = t; &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (a[e3] &lt; a[e2]) &#123; <span class="keyword">int</span> t = a[e3]; a[e3] = a[e2]; a[e2] = t;</span><br><span class="line">	    <span class="keyword">if</span> (t &lt; a[e1]) &#123; a[e2] = a[e1]; a[e1] = t; &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (a[e4] &lt; a[e3]) &#123; <span class="keyword">int</span> t = a[e4]; a[e4] = a[e3]; a[e3] = t;</span><br><span class="line">	    <span class="keyword">if</span> (t &lt; a[e2]) &#123; a[e3] = a[e2]; a[e2] = t;</span><br><span class="line">		    <span class="keyword">if</span> (t &lt; a[e1]) &#123; a[e2] = a[e1]; a[e1] = t; &#125;</span><br><span class="line">	    &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (a[e5] &lt; a[e4]) &#123; <span class="keyword">int</span> t = a[e5]; a[e5] = a[e4]; a[e4] = t;</span><br><span class="line">	    <span class="keyword">if</span> (t &lt; a[e3]) &#123; a[e4] = a[e3]; a[e3] = t;</span><br><span class="line">		    <span class="keyword">if</span> (t &lt; a[e2]) &#123; a[e3] = a[e2]; a[e2] = t;</span><br><span class="line">			    <span class="keyword">if</span> (t &lt; a[e1]) &#123; a[e2] = a[e1]; a[e1] = t; &#125;</span><br><span class="line">		    &#125;</span><br><span class="line">	    &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Pointers</span></span><br><span class="line">    <span class="comment">// 指针</span></span><br><span class="line">    <span class="keyword">int</span> less  = left;  <span class="comment">// The index of the first element of center part（less为center部分的头指针）</span></span><br><span class="line">    <span class="keyword">int</span> great = right; <span class="comment">// The index before the first element of right part（great为right部分的头指针的前一个指针）</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 分割点不全相等</span></span><br><span class="line">    <span class="keyword">if</span> (a[e1] != a[e2] &amp;&amp; a[e2] != a[e3] &amp;&amp; a[e3] != a[e4] &amp;&amp; a[e4] != a[e5]) &#123;</span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * Use the second and fourth of the five sorted elements as pivots.</span></span><br><span class="line"><span class="comment">	     * These values are inexpensive approximations of the first and</span></span><br><span class="line"><span class="comment">	     * second terciles of the array. Note that pivot1 &lt;= pivot2.</span></span><br><span class="line"><span class="comment">	     * 选取第二个和第四个分割元素作枢轴。</span></span><br><span class="line"><span class="comment">	     * pivot1 &lt;= pivot2</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    <span class="keyword">int</span> pivot1 = a[e2];</span><br><span class="line">	    <span class="keyword">int</span> pivot2 = a[e4];</span><br><span class="line"></span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * The first and the last elements to be sorted are moved to the</span></span><br><span class="line"><span class="comment">	     * locations formerly occupied by the pivots. When partitioning</span></span><br><span class="line"><span class="comment">	     * is complete, the pivots are swapped back into their final</span></span><br><span class="line"><span class="comment">	     * positions, and excluded from subsequent sorting.</span></span><br><span class="line"><span class="comment">	     * 将要进行排序的第一个和最后一个元素移动到之前选中枢轴所在的位置。</span></span><br><span class="line"><span class="comment">	     * 当划分结束，枢轴元素会被重新交换回最终位置，并从后续排序中排除。</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    a[e2] = a[left];</span><br><span class="line">	    a[e4] = a[right];</span><br><span class="line"></span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * Skip elements, which are less or greater than pivot values.</span></span><br><span class="line"><span class="comment">	     * 跳过有序元素。</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    <span class="keyword">while</span> (a[++less] &lt; pivot1);</span><br><span class="line">	    <span class="keyword">while</span> (a[--great] &gt; pivot2);</span><br><span class="line"></span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * Partitioning:</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     *   left part           center part                   right part</span></span><br><span class="line"><span class="comment">	     * +--------------------------------------------------------------+</span></span><br><span class="line"><span class="comment">	     * |  &lt; pivot1  |  pivot1 &lt;= &amp;&amp; &lt;= pivot2  |    ?    |  &gt; pivot2  |</span></span><br><span class="line"><span class="comment">	     * +--------------------------------------------------------------+</span></span><br><span class="line"><span class="comment">	     *               ^                          ^       ^</span></span><br><span class="line"><span class="comment">	     *               |                          |       |</span></span><br><span class="line"><span class="comment">	     *              less                        k     great</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     * Invariants:</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     *              all in (left, less)   &lt; pivot1</span></span><br><span class="line"><span class="comment">	     *    pivot1 &lt;= all in [less, k)     &lt;= pivot2</span></span><br><span class="line"><span class="comment">	     *              all in (great, right) &gt; pivot2</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     * Pointer k is the first index of ?-part.</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     * 将数组分成四部分</span></span><br><span class="line"><span class="comment">	     * 	 左部：i &lt; p1</span></span><br><span class="line"><span class="comment">	     *	 中部：p1 &lt;= i &lt;= p2</span></span><br><span class="line"><span class="comment">	     * 	 未比较部分</span></span><br><span class="line"><span class="comment">	     * 	 右部：i &gt; p2</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    outer:</span><br><span class="line">        <span class="comment">// 记给自己，k赋初值后，要先进行自加比较</span></span><br><span class="line">	    <span class="keyword">for</span> (<span class="keyword">int</span> k = less - <span class="number">1</span>; ++k &lt;= great; ) &#123;</span><br><span class="line">		    <span class="keyword">int</span> ak = a[k];</span><br><span class="line">             <span class="comment">// 比p1小的移到左边部分</span></span><br><span class="line">		    <span class="keyword">if</span> (ak &lt; pivot1) &#123; <span class="comment">// Move a[k] to left part</span></span><br><span class="line">			    a[k] = a[less];</span><br><span class="line">			    <span class="comment">/*</span></span><br><span class="line"><span class="comment">			     * Here and below we use &quot;a[i] = b; i++;&quot; instead</span></span><br><span class="line"><span class="comment">			     * of &quot;a[i++] = b;&quot; due to performance issue.</span></span><br><span class="line"><span class="comment">			     */</span></span><br><span class="line">			    a[less] = ak;</span><br><span class="line">			    ++less;</span><br><span class="line">             <span class="comment">// 比p2大的移到右边部分</span></span><br><span class="line">		    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (ak &gt; pivot2) &#123; <span class="comment">// Move a[k] to right part</span></span><br><span class="line">			    <span class="comment">// 移动great指针直到其对应的元素小于p2</span></span><br><span class="line">                 <span class="keyword">while</span> (a[great] &gt; pivot2) &#123;</span><br><span class="line">				    <span class="keyword">if</span> (great-- == k) &#123;</span><br><span class="line">					    <span class="keyword">break</span> outer;</span><br><span class="line">				    &#125;</span><br><span class="line">			    &#125;</span><br><span class="line">                 <span class="comment">// great指向的元素小于p1，交换a[great]、a[less]，并将less指针+1</span></span><br><span class="line">			    <span class="keyword">if</span> (a[great] &lt; pivot1) &#123; <span class="comment">// a[great] &lt;= pivot2</span></span><br><span class="line">				    a[k] = a[less];</span><br><span class="line">				    a[less] = a[great];</span><br><span class="line">				    ++less;</span><br><span class="line">                 <span class="comment">// pivot1 &lt;= a[great] &lt;= pivot2，处于p1、p2之间，放到k位置</span></span><br><span class="line">			    &#125; <span class="keyword">else</span> &#123; <span class="comment">// pivot1 &lt;= a[great] &lt;= pivot2</span></span><br><span class="line">				    a[k] = a[great];</span><br><span class="line">			    &#125;</span><br><span class="line">			    <span class="comment">/*</span></span><br><span class="line"><span class="comment">			     * Here and below we use &quot;a[i] = b; i--;&quot; instead</span></span><br><span class="line"><span class="comment">			     * of &quot;a[i--] = b;&quot; due to performance issue.</span></span><br><span class="line"><span class="comment">			     */</span></span><br><span class="line">			    a[great] = ak;</span><br><span class="line">			    --great;</span><br><span class="line">		    &#125;</span><br><span class="line">	    &#125;</span><br><span class="line"></span><br><span class="line">	    <span class="comment">// Swap pivots into their final positions</span></span><br><span class="line">        <span class="comment">// 交换枢轴至他们最终的位置</span></span><br><span class="line">	    a[left]  = a[less  - <span class="number">1</span>]; a[less  - <span class="number">1</span>] = pivot1;</span><br><span class="line">	    a[right] = a[great + <span class="number">1</span>]; a[great + <span class="number">1</span>] = pivot2;</span><br><span class="line"></span><br><span class="line">	    <span class="comment">// Sort left and right parts recursively, excluding known pivots</span></span><br><span class="line">        <span class="comment">// 递归排序左右部分，包括已知的枢轴</span></span><br><span class="line">	    sort(a, left, less - <span class="number">2</span>, leftmost);</span><br><span class="line">	    sort(a, great + <span class="number">2</span>, right, <span class="keyword">false</span>);</span><br><span class="line"></span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * If center part is too large (comprises &gt; 4/7 of the array),</span></span><br><span class="line"><span class="comment">	     * swap internal pivot values to ends.</span></span><br><span class="line"><span class="comment">	     * 如果中心部分超出数组的4/7，将内部的枢轴值交换至末端。</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    <span class="keyword">if</span> (less &lt; e1 &amp;&amp; e5 &lt; great) &#123;</span><br><span class="line">		    <span class="comment">/*</span></span><br><span class="line"><span class="comment">		     * Skip elements, which are equal to pivot values.</span></span><br><span class="line"><span class="comment">		     */</span></span><br><span class="line">		    <span class="keyword">while</span> (a[less] == pivot1) &#123;</span><br><span class="line">			    ++less;</span><br><span class="line">		    &#125;</span><br><span class="line"></span><br><span class="line">		    <span class="keyword">while</span> (a[great] == pivot2) &#123;</span><br><span class="line">			    --great;</span><br><span class="line">		    &#125;</span><br><span class="line"></span><br><span class="line">		    <span class="comment">/*</span></span><br><span class="line"><span class="comment">		     * Partitioning:</span></span><br><span class="line"><span class="comment">		     *</span></span><br><span class="line"><span class="comment">		     *   left part         center part                  right part</span></span><br><span class="line"><span class="comment">		     * +----------------------------------------------------------+</span></span><br><span class="line"><span class="comment">		     * | == pivot1 |  pivot1 &lt; &amp;&amp; &lt; pivot2  |    ?    | == pivot2 |</span></span><br><span class="line"><span class="comment">		     * +----------------------------------------------------------+</span></span><br><span class="line"><span class="comment">		     *              ^                        ^       ^</span></span><br><span class="line"><span class="comment">		     *              |                        |       |</span></span><br><span class="line"><span class="comment">		     *             less                      k     great</span></span><br><span class="line"><span class="comment">		     *</span></span><br><span class="line"><span class="comment">		     * Invariants:</span></span><br><span class="line"><span class="comment">		     *</span></span><br><span class="line"><span class="comment">		     *              all in (*,  less) == pivot1</span></span><br><span class="line"><span class="comment">		     *     pivot1 &lt; all in [less,  k)  &lt; pivot2</span></span><br><span class="line"><span class="comment">		     *              all in (great, *) == pivot2</span></span><br><span class="line"><span class="comment">		     *</span></span><br><span class="line"><span class="comment">		     * Pointer k is the first index of ?-part.</span></span><br><span class="line"><span class="comment">		     */</span></span><br><span class="line">		    outer:</span><br><span class="line">		    <span class="keyword">for</span> (<span class="keyword">int</span> k = less - <span class="number">1</span>; ++k &lt;= great; ) &#123;</span><br><span class="line">			    <span class="keyword">int</span> ak = a[k];</span><br><span class="line">			    <span class="keyword">if</span> (ak == pivot1) &#123; <span class="comment">// Move a[k] to left part</span></span><br><span class="line">				    a[k] = a[less];</span><br><span class="line">				    a[less] = ak;</span><br><span class="line">				    ++less;</span><br><span class="line">			    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (ak == pivot2) &#123; <span class="comment">// Move a[k] to right part</span></span><br><span class="line">				    <span class="keyword">while</span> (a[great] == pivot2) &#123;</span><br><span class="line">					    <span class="keyword">if</span> (great-- == k) &#123;</span><br><span class="line">						    <span class="keyword">break</span> outer;</span><br><span class="line">					    &#125;</span><br><span class="line">				    &#125;</span><br><span class="line">				    <span class="keyword">if</span> (a[great] == pivot1) &#123; <span class="comment">// a[great] &lt; pivot2</span></span><br><span class="line">					    a[k] = a[less];</span><br><span class="line">					    <span class="comment">/*</span></span><br><span class="line"><span class="comment">					     * Even though a[great] equals to pivot1, the</span></span><br><span class="line"><span class="comment">					     * assignment a[less] = pivot1 may be incorrect,</span></span><br><span class="line"><span class="comment">					     * if a[great] and pivot1 are floating-point zeros</span></span><br><span class="line"><span class="comment">					     * of different signs. Therefore in float and</span></span><br><span class="line"><span class="comment">					     * double sorting methods we have to use more</span></span><br><span class="line"><span class="comment">					     * accurate assignment a[less] = a[great].</span></span><br><span class="line"><span class="comment">					     */</span></span><br><span class="line">					    a[less] = pivot1;</span><br><span class="line">					    ++less;</span><br><span class="line">				    &#125; <span class="keyword">else</span> &#123; <span class="comment">// pivot1 &lt; a[great] &lt; pivot2</span></span><br><span class="line">					    a[k] = a[great];</span><br><span class="line">				    &#125;</span><br><span class="line">				    a[great] = ak;</span><br><span class="line">				    --great;</span><br><span class="line">			    &#125;</span><br><span class="line">		    &#125;</span><br><span class="line">	    &#125;</span><br><span class="line"></span><br><span class="line">	    <span class="comment">// Sort center part recursively</span></span><br><span class="line">	    sort(a, less, great, <span class="keyword">false</span>);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 长度在4/7之内，使用单轴快排</span></span><br><span class="line">    &#125; <span class="keyword">else</span> &#123; <span class="comment">// Partitioning with one pivot</span></span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * Use the third of the five sorted elements as pivot.</span></span><br><span class="line"><span class="comment">	     * This value is inexpensive approximation of the median.</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    <span class="keyword">int</span> pivot = a[e3];</span><br><span class="line"></span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * Partitioning degenerates to the traditional 3-way</span></span><br><span class="line"><span class="comment">	     * (or &quot;Dutch National Flag&quot;) schema:</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     *   left part    center part              right part</span></span><br><span class="line"><span class="comment">	     * +-------------------------------------------------+</span></span><br><span class="line"><span class="comment">	     * |  &lt; pivot  |   == pivot   |     ?    |  &gt; pivot  |</span></span><br><span class="line"><span class="comment">	     * +-------------------------------------------------+</span></span><br><span class="line"><span class="comment">	     *              ^              ^        ^</span></span><br><span class="line"><span class="comment">	     *              |              |        |</span></span><br><span class="line"><span class="comment">	     *             less            k      great</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     * Invariants:</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     *   all in (left, less)   &lt; pivot</span></span><br><span class="line"><span class="comment">	     *   all in [less, k)     == pivot</span></span><br><span class="line"><span class="comment">	     *   all in (great, right) &gt; pivot</span></span><br><span class="line"><span class="comment">	     *</span></span><br><span class="line"><span class="comment">	     * Pointer k is the first index of ?-part.</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    <span class="keyword">for</span> (<span class="keyword">int</span> k = less; k &lt;= great; ++k) &#123;</span><br><span class="line">		    <span class="keyword">if</span> (a[k] == pivot) &#123;</span><br><span class="line">			    <span class="keyword">continue</span>;</span><br><span class="line">		    &#125;</span><br><span class="line">		    <span class="keyword">int</span> ak = a[k];</span><br><span class="line">		    <span class="keyword">if</span> (ak &lt; pivot) &#123; <span class="comment">// Move a[k] to left part</span></span><br><span class="line">			    a[k] = a[less];</span><br><span class="line">			    a[less] = ak;</span><br><span class="line">			    ++less;</span><br><span class="line">		    &#125; <span class="keyword">else</span> &#123; <span class="comment">// a[k] &gt; pivot - Move a[k] to right part</span></span><br><span class="line">			    <span class="keyword">while</span> (a[great] &gt; pivot) &#123;</span><br><span class="line">				    --great;</span><br><span class="line">			    &#125;</span><br><span class="line">			    <span class="keyword">if</span> (a[great] &lt; pivot) &#123; <span class="comment">// a[great] &lt;= pivot</span></span><br><span class="line">				    a[k] = a[less];</span><br><span class="line">				    a[less] = a[great];</span><br><span class="line">				    ++less;</span><br><span class="line">			    &#125; <span class="keyword">else</span> &#123; <span class="comment">// a[great] == pivot</span></span><br><span class="line">				    <span class="comment">/*</span></span><br><span class="line"><span class="comment">				     * Even though a[great] equals to pivot, the</span></span><br><span class="line"><span class="comment">				     * assignment a[k] = pivot may be incorrect,</span></span><br><span class="line"><span class="comment">				     * if a[great] and pivot are floating-point</span></span><br><span class="line"><span class="comment">				     * zeros of different signs. Therefore in float</span></span><br><span class="line"><span class="comment">				     * and double sorting methods we have to use</span></span><br><span class="line"><span class="comment">				     * more accurate assignment a[k] = a[great].</span></span><br><span class="line"><span class="comment">				     */</span></span><br><span class="line">				    a[k] = pivot;</span><br><span class="line">			    &#125;</span><br><span class="line">			    a[great] = ak;</span><br><span class="line">			    --great;</span><br><span class="line">		    &#125;</span><br><span class="line">	    &#125;</span><br><span class="line"></span><br><span class="line">	    <span class="comment">/*</span></span><br><span class="line"><span class="comment">	     * Sort left and right parts recursively.</span></span><br><span class="line"><span class="comment">	     * All elements from center part are equal</span></span><br><span class="line"><span class="comment">	     * and, therefore, already sorted.</span></span><br><span class="line"><span class="comment">	     */</span></span><br><span class="line">	    sort(a, left, less - <span class="number">1</span>, leftmost);</span><br><span class="line">	    sort(a, great + <span class="number">1</span>, right, <span class="keyword">false</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><div class="gallery ">
              <p><img src="https://typora-yayako.oss-cn-hangzhou.aliyuncs.com/Arrays.sort().png" class="lazyload" data-srcset="https://typora-yayako.oss-cn-hangzhou.aliyuncs.com/Arrays.sort().png" srcset="" alt="Arrays.sort()"></p>
            </div>

  
  
    
    <div class='footer'>
      
      
      
        <div class='copyright'>
          <blockquote>
            
              
                <p>博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</p>

              
            
              
                <p>本文永久链接是：<a href=https://www.yayako.cn/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/>https://www.yayako.cn/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/</a></p>
              
            
          </blockquote>
        </div>
      
      
    </div>
  
  
    


  <div class='article-meta' id="bottom">
    <div class='new-meta-box'>
      
        
          <div class="new-meta-item date" itemprop="dateUpdated" datetime="2021-01-23T00:30:32+08:00">
  <a class='notlink'>
    <i class="fas fa-edit fa-fw" aria-hidden="true"></i>
    <p>更新于：2021年1月23日</p>
  </a>
</div>

        
      
        
          
  
  <div class="new-meta-item meta-tags"><a class="tag" href="/tags/Java/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>Java</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/%E6%BA%90%E7%A0%81/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>源码</p></a></div>


        
      
        
          
  <div class="new-meta-item share -mob-share-list">
  <div class="-mob-share-list share-body">
    
      
        <a class="-mob-share-qq" title="" rel="external nofollow noopener noreferrer noopener"
          
          target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://www.yayako.cn/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/&title=Arrays.sort()源码解读+流程图总结 - Yayako's Blog&summary=Java中Arrays.sort()源码的跟踪注释，重点在归并排序和快速排序两点，最后画了流程图做总结。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qq.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qq.png" srcset="">
          
        </a>
      
    
      
        <a class="-mob-share-qzone" title="" rel="external nofollow noopener noreferrer noopener"
          
          target="_blank" href="https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?url=https://www.yayako.cn/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/&title=Arrays.sort()源码解读+流程图总结 - Yayako's Blog&summary=Java中Arrays.sort()源码的跟踪注释，重点在归并排序和快速排序两点，最后画了流程图做总结。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qzone.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qzone.png" srcset="">
          
        </a>
      
    
      
        <a class="-mob-share-weibo" title="" rel="external nofollow noopener noreferrer noopener"
          
          target="_blank" href="http://service.weibo.com/share/share.php?url=https://www.yayako.cn/2020/01/22/Arrays-sort-%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB-%E6%B5%81%E7%A8%8B%E5%9B%BE%E6%80%BB%E7%BB%93/&title=Arrays.sort()源码解读+流程图总结 - Yayako's Blog&summary=Java中Arrays.sort()源码的跟踪注释，重点在归并排序和快速排序两点，最后画了流程图做总结。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/weibo.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/weibo.png" srcset="">
          
        </a>
      
    
      
    
      
    
  </div>
</div>



        
      
    </div>
  </div>


  
  

  
    <div class="prev-next">
      
        <a class='prev' href='/2020/01/22/%E6%9C%89%E5%85%B3String%E7%9A%84%E5%87%A0%E4%B8%AA%E9%97%AE%E9%A2%98%EF%BC%88%E7%BB%93%E5%90%88JVM%EF%BC%89/'>
          <p class='title'><i class="fas fa-chevron-left" aria-hidden="true"></i>有关String的几个问题（结合JVM）</p>
          <p class='content'>有关String的几个问题（结合JVM）首先明确字符串常量存储的位置，字符串在Java虚拟机中是存储在字符串常量池中的，而在jdk7之前，字符串常量池存在于永久代（也就是方法区）中，在jdk7开...</p>
        </a>
      
      
    </div>
  
</article>


  

  <article class="post white-box reveal shadow" id="comments">
    <p ct><i class='fas fa-comments'></i> 评论</p>
    
    <div id="valine_container" class="valine_thread">
  <i class="fas fa-cog fa-spin fa-fw fa-2x"></i>
</div>

  </article>






</div>
<aside class='l_side'>
  
  
    
    



  <section class="widget toc-wrapper shadow desktop mobile" id="toc-div" >
    
  <header>
    
      <i class="fas fa-list fa-fw" aria-hidden="true"></i><span class='name'>本文目录</span>
    
  </header>


    <div class='content'>
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#Arrays-sort"><span class="toc-text">Arrays.sort()</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#DualPivotQuicksort-sort"><span class="toc-text">DualPivotQuicksort.sort()</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BD%92%E5%B9%B6%E9%83%A8%E5%88%86"><span class="toc-text">归并部分</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BF%AB%E6%8E%92%E9%83%A8%E5%88%86"><span class="toc-text">快排部分</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%BB%E7%BB%93"><span class="toc-text">总结</span></a></li></ol>
    </div>
  </section>


  


</aside>


   <!--此文件用来存放一些不方便取值的变量-->
<!--思路大概是将值藏到重加载的区域内-->

<script>
  window.pdata={}
  pdata.ispage=true;
  pdata.postTitle="Arrays.sort()源码解读+流程图总结";
  pdata.commentPath="";
  pdata.commentPlaceholder="";

  var l_header=document.getElementById("l_header");
  
  l_header.classList.remove("show");
  
</script>
 
        </div>
        
  
  <footer class="footer clearfix">
    <br><br>
    
      
        <div class="aplayer-container">
          


        </div>
      
    
      
        <br>
        <div class="social-wrapper">
          
            
          
            
          
            
          
        </div>
      
    
      
        <div><p>博客内容遵循 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</a></p>
</div>
      
    
      
        
          <div><p><span id="lc-sv">本站总访问量为 <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span> 次</span> <span id="lc-uv">访客数为 <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span> 人</span></p>
</div>
        
      
    
      
        
      
    
      
        <div class='copyright'>
        <p><a href="/about/">Copyright © 2021 扭秧歌的一只泱</a> <strong>|</strong> <img src="https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/%E5%A4%87%E6%A1%88%E5%9B%BE%E6%A0%87.png" class="lazyload" data-srcset="https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/%E5%A4%87%E6%A1%88%E5%9B%BE%E6%A0%87.png" srcset="" alt="备案图标"> <a target="_blank" rel="noopener" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=33032402002017">浙公网安备33032402002017号</a> <strong>|</strong> <a target="_blank" rel="noopener" href="https://beian.miit.gov.cn/#/Integrated/index">浙ICP备20015559号</a></p>

        </div>
      
    
  </footer>


        <a
          id="s-top"
          class="fas fa-arrow-up fa-fw"
          href="javascript:void(0)"
        ></a>
      </div>
    </div>
    <div>
      <script>
window.volantis={};
window.volantis.loadcss=document.getElementById("loadcss");
/********************脚本懒加载函数********************************/
function loadScript(src, cb) {
var HEAD = document.getElementsByTagName('head')[0] || document.documentElement;
var script = document.createElement('script');
script.setAttribute('type','text/javascript');
if (cb) script.onload = cb;
script.setAttribute('src', src);
HEAD.appendChild(script);
}
//https://github.com/filamentgroup/loadCSS
var loadCSS = function( href, before, media, attributes ){
	var doc = window.document;
	var ss = doc.createElement( "link" );
	var ref;
	if( before ){
		ref = before;
	}
	else {
		var refs = ( doc.body || doc.getElementsByTagName( "head" )[ 0 ] ).childNodes;
		ref = refs[ refs.length - 1];
	}
	var sheets = doc.styleSheets;
	if( attributes ){
		for( var attributeName in attributes ){
			if( attributes.hasOwnProperty( attributeName ) ){
				ss.setAttribute( attributeName, attributes[attributeName] );
			}
		}
	}
	ss.rel = "stylesheet";
	ss.href = href;
	ss.media = "only x";
	function ready( cb ){
		if( doc.body ){
			return cb();
		}
		setTimeout(function(){
			ready( cb );
		});
	}
	ready( function(){
		ref.parentNode.insertBefore( ss, ( before ? ref : ref.nextSibling ) );
	});
	var onloadcssdefined = function( cb ){
		var resolvedHref = ss.href;
		var i = sheets.length;
		while( i-- ){
			if( sheets[ i ].href === resolvedHref ){
				return cb();
			}
		}
		setTimeout(function() {
			onloadcssdefined( cb );
		});
	};
	function loadCB(){
		if( ss.addEventListener ){
			ss.removeEventListener( "load", loadCB );
		}
		ss.media = media || "all";
	}
	if( ss.addEventListener ){
		ss.addEventListener( "load", loadCB);
	}
	ss.onloadcssdefined = onloadcssdefined;
	onloadcssdefined( loadCB );
	return ss;
};
</script>
<script>
  
  loadCSS("https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14/css/all.min.css", window.volantis.loadcss);
  
  
  
  
</script>
<!-- required -->

<script src="https://cdn.jsdelivr.net/npm/jquery@3.5/dist/jquery.min.js"></script>

<script>
  function pjax_fancybox() {
    $(".md .gallery").find("img").each(function () { //渲染 fancybox
      var element = document.createElement("a"); // a 标签
      $(element).attr("class", "fancybox");
      $(element).attr("pjax-fancybox", "");  // 过滤 pjax
      $(element).attr("href", $(this).attr("src"));
      if ($(this).attr("data-original")) {
        $(element).attr("href", $(this).attr("data-original"));
      }
      $(element).attr("data-fancybox", "images");
      var caption = "";   // 描述信息
      if ($(this).attr('alt')) {  // 判断当前页面是否存在描述信息
        $(element).attr('data-caption', $(this).attr('alt'));
        caption = $(this).attr('alt');
      }
      var div = document.createElement("div");
      $(div).addClass("fancybox");
      $(this).wrap(div); // 最外层套 div ，其实主要作用还是 class 样式
      var span = document.createElement("span");
      $(span).addClass("image-caption");
      $(span).text(caption); // 加描述
      $(this).after(span);  // 再套一层描述
      $(this).wrap(element);  // 最后套 a 标签
    })
    $(".md .gallery").find("img").fancybox({
      selector: '[data-fancybox="images"]',
      hash: false,
      loop: false,
      closeClick: true,
      helpers: {
        overlay: {closeClick: true}
      },
      buttons: [
        "zoom",
        "close"
      ]
    });
  };
  function SCload_fancybox() {
    if ($(".md .gallery").find("img").length == 0) return;
    loadCSS("https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css", document.getElementById("loadcss"));
    setTimeout(function() {
      loadScript('https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js', pjax_fancybox)
    }, 1);
  };
  $(function () {
    SCload_fancybox();
  });
</script>


<!-- internal -->

  
  
  
    
<script src="https://cdn.jsdelivr.net/npm/jquery-backstretch@2.1.18/jquery.backstretch.min.js"></script>

    <script type="text/javascript">
        var imgs=["https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/cover/hd.jpg"];
        if ('false' == 'true') {
          function shuffle(arr){
            /*From countercurrent-time*/
            var n = arr.length;
            while(n--) {
              var index = Math.floor(Math.random() * n);
              var temp = arr[index];
              arr[index] = arr[n];
              arr[n] = temp;
            }
          }
          shuffle(imgs);
        }
	  function Pjax_backstretch(){
        
          $.backstretch(
            imgs,
          {
            duration: "10000",
            fade: "1500"
          });
        
	  }
	  loadScript("https://cdn.jsdelivr.net/npm/jquery-backstretch@2.1.18/jquery.backstretch.min.js",Pjax_backstretch)
    </script>
  




<script>
  function loadIssuesJS() {
    if ($(".md").find(".issues-api").length == 0) return;
    setTimeout(function() {
	
	  loadScript('/js/issues.js');
	
    }, 1);
  };
  $(function () {
    loadIssuesJS();
  });
</script>



  <script defer src="https://cdn.jsdelivr.net/npm/vanilla-lazyload@17.1.0/dist/lazyload.min.js"></script>
<script>
  // https://www.npmjs.com/package/vanilla-lazyload
  // Set the options globally
  // to make LazyLoad self-initialize
  window.lazyLoadOptions = {
    elements_selector: ".lazyload",
    threshold: 0
  };
  // Listen to the initialization event
  // and get the instance of LazyLoad
  window.addEventListener(
    "LazyLoad::Initialized",
    function (event) {
      window.lazyLoadInstance = event.detail.instance;
    },
    false
  );
  document.addEventListener('DOMContentLoaded', function () {
    lazyLoadInstance.update();
  });
  document.addEventListener('pjax:complete', function () {
    lazyLoadInstance.update();
  });
</script>




  
  
    <script>
      window.FPConfig = {
        delay: 0,
        ignoreKeywords: [],
        maxRPS: 5,
        hoverDelay: 25
      };
    </script>
    <script defer src="https://cdn.jsdelivr.net/gh/gijo-varghese/flying-pages@2.1.2/flying-pages.min.js"></script>
  




  <script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
    var clipboard = new ClipboardJS('.btn-copy', {
        target: function (trigger) {
            return trigger.nextElementSibling
        }
    });
    function wait(callback, seconds) {
        var timelag = null;
        timelag = window.setTimeout(callback, seconds)
    }
    function pjax_initCopyCode() {
		if($(".highlight .code pre").length+$(".article pre code").length==0)return;
        var copyHtml = '';
        copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
        copyHtml += '<i class="fas fa-copy"></i><span>COPY</span>';
        copyHtml += '</button>';
        $(".highlight .code pre").before(copyHtml);
        $(".article pre code").before(copyHtml);
        clipboard.off('success').on('success', function (e) {
            let $btn = $(e.trigger);
            $btn.addClass('copied');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-check-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPIED';
            wait(function () {
                $icon.removeClass('fa-check-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        });
        clipboard.off('error').on('error', function (e) {
            e.clearSelection();
            let $btn = $(e.trigger);
            $btn.addClass('copy-failed');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-times-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPY FAILED';
            wait(function () {
                $icon.removeClass('fa-times-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        })
    }
    $(function () {
        pjax_initCopyCode()
    });
</script>




   <script src="https://cdn.jsdelivr.net/npm/scrollreveal@4.0.6/dist/scrollreveal.min.js"></script>
<script type="text/javascript">
  function pjax_scrollrebeal() {
    ScrollReveal().reveal('.l_main .reveal', {
      distance: '32px',
      duration: '800',
      interval: '20',
      scale: '1',
      easing: 'ease-out'
    });
  }
  $(function () {
    pjax_scrollrebeal();
  });
</script>






  
  
<script src="https://cdn.jsdelivr.net/npm/valine@1.4/dist/Valine.min.js"></script>


<script>
  function emoji(path, idx, ext) {
    return path + "/" + path + "-" + idx + "." + ext;
  }
  var emojiMaps = {};
  for (var i = 1; i <= 54; i++) {
    emojiMaps['tieba-' + i] = emoji('tieba', i, 'png');
  }
  for (var i = 1; i <= 101; i++) {
    emojiMaps['qq-' + i] = emoji('qq', i, 'gif');
  }
  for (var i = 1; i <= 116; i++) {
    emojiMaps['aru-' + i] = emoji('aru', i, 'gif');
  }
  for (var i = 1; i <= 125; i++) {
    emojiMaps['twemoji-' + i] = emoji('twemoji', i, 'png');
  }
  for (var i = 1; i <= 4; i++) {
    emojiMaps['weibo-' + i] = emoji('weibo', i, 'png');
  }
  function pjax_valine() {
    if(!document.querySelectorAll("#valine_container")[0])return;
    let pagePlaceholder = pdata.commentPlaceholder || "快来评论吧~";
    let path = pdata.commentPath;
    if (path.length == 0) {
      let defaultPath = '';
      path = defaultPath || decodeURI(window.location.pathname);
    }
    var valine = new Valine();
    valine.init(Object.assign({"js":"https://cdn.jsdelivr.net/npm/valine@1.4/dist/Valine.min.js","path":null,"placeholder":"快来评论吧~","appId":"crkoKrezsl4I7UWQjAvOy2N1-gzGzoHsz","appKey":"OUvAeTn1CnCmGFdNYVH00G0S","meta":["nick","mail","link"],"requiredFields":["nick","mail"],"enableQQ":true,"recordIP":false,"avatar":"robohash","pageSize":10,"lang":"zh-cn","highlight":true,"visitor":true,"mathJax":false}, {
      el: '#valine_container',
      path: path,
      placeholder: pagePlaceholder,
      emojiCDN: 'https://cdn.jsdelivr.net/gh/volantis-x/cdn-emoji/valine/',
      emojiMaps: emojiMaps,
    }))
  }
  $(function () {
    pjax_valine();
  });
</script>





  
<script src="/js/app.js"></script>



<!-- optional -->

  <script>
const SearchServiceimagePath="https://cdn.jsdelivr.net/gh/volantis-x/cdn-volantis@master/img/";
const ROOT =  ("/" || "/").endsWith('/') ? ("/" || "/") : ("//" || "/" );

$('.input.u-search-input').one('focus',function(){
	
		loadScript('/js/search/hexo.js',setSearchService);
	
})

function listenSearch(){
  
    customSearch = new HexoSearch({
      imagePath: SearchServiceimagePath
    });
  
}
function setSearchService() {
	listenSearch();
	
		document.addEventListener("pjax:success", listenSearch);
	
}
</script>











  <script defer>

  const LCCounter = {
    app_id: 'u9j57bwJod4EDmXWdxrwuqQT-MdYXbMMI',
    app_key: 'jfHtEKVE24j0IVCGHbvuFClp',
    custom_api_server: '',

    // 查询存储的记录
    getRecord(Counter, url, title) {
      return new Promise(function (resolve, reject) {
        Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({url})))
          .then(resp => resp.json())
          .then(({results, code, error}) => {
            if (code === 401) {
              throw error;
            }
            if (results && results.length > 0) {
              var record = results[0];
              resolve(record);
            } else {
              Counter('post', '/classes/Counter', {url, title: title, times: 0})
                .then(resp => resp.json())
                .then((record, error) => {
                  if (error) {
                    throw error;
                  }
                  resolve(record);
                }).catch(error => {
                console.error('Failed to create', error);
                reject(error);
              });
            }
          }).catch((error) => {
          console.error('LeanCloud Counter Error:', error);
          reject(error);
        });
      })
    },

    // 发起自增请求
    increment(Counter, incrArr) {
      return new Promise(function (resolve, reject) {
        Counter('post', '/batch', {
          "requests": incrArr
        }).then((res) => {
          res = res.json();
          if (res.error) {
            throw res.error;
          }
          resolve(res);
        }).catch((error) => {
          console.error('Failed to save visitor count', error);
          reject(error);
        });
      });
    },

    // 构建自增请求体
    buildIncrement(objectId) {
      return {
        "method": "PUT",
        "path": `/1.1/classes/Counter/${ objectId }`,
        "body": {
          "times": {
            '__op': 'Increment',
            'amount': 1
          }
        }
      }
    },

    // 校验是否为有效的 UV
    validUV() {
      var key = 'LeanCloudUVTimestamp';
      var flag = localStorage.getItem(key);
      if (flag) {
        // 距离标记小于 24 小时则不计为 UV
        if (new Date().getTime() - parseInt(flag) <= 86400000) {
          return false;
        }
      }
      localStorage.setItem(key, new Date().getTime().toString());
      return true;
    },

    addCount(Counter) {
      var enableIncr = '' === 'true' && window.location.hostname !== 'localhost';
      enableIncr = true;
      var getterArr = [];
      var incrArr = [];
      // 请求 PV 并自增
      var pvCtn = document.querySelector('#lc-sv');
      if (pvCtn || enableIncr) {
        var pvGetter = this.getRecord(Counter, 'https://www.yayako.cn' + '/#lc-sv', 'Visits').then((record) => {
          incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-sv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + 1;
              if (pvCtn) {
                pvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(pvGetter);
      }

      // 请求 UV 并自增
      var uvCtn = document.querySelector('#lc-uv');
      if (uvCtn || enableIncr) {
        var uvGetter = this.getRecord(Counter, 'https://www.yayako.cn' + '/#lc-uv', 'Visitors').then((record) => {
          var vuv = this.validUV();
          vuv && incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-uv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + (vuv ? 1 : 0);
              if (uvCtn) {
                uvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(uvGetter);
      }

      // 请求文章的浏览数，如果是当前页面就自增
      var allPV = document.querySelectorAll('#lc-pv');
      if (allPV.length > 0 || enableIncr) {
        for (i = 0; i < allPV.length; i++) {
          let pv = allPV[i];
          let title = pv.getAttribute('data-title');
          var url = 'https://www.yayako.cn' + pv.getAttribute('data-path');
          if (url) {
            var viewGetter = this.getRecord(Counter, url, title).then((record) => {
              // 是当前页面就自增
              let curPath = window.location.pathname;
              if (curPath.includes('index.html')) {
                curPath = curPath.substring(0, curPath.lastIndexOf('index.html'));
              }
              if (pv.getAttribute('data-path') == curPath) {
                incrArr.push(this.buildIncrement(record.objectId));
              }
              if (pv) {
                var ele = pv.querySelector('#lc-pv #number');
                if (ele) {
                  if (pv.getAttribute('data-path') == curPath) {
                    ele.innerText = (record.times || 0) + 1;
                  } else {
                    ele.innerText = record.times || 0;
                  }
                  pv.style.display = 'inline';
                }
              }
            });
            getterArr.push(viewGetter);
          }
        }
      }

      // 如果启动计数自增，批量发起自增请求
      if (enableIncr) {
        Promise.all(getterArr).then(() => {
          incrArr.length > 0 && this.increment(Counter, incrArr);
        })
      }

    },


    fetchData(api_server) {
      var Counter = (method, url, data) => {
        return fetch(`${ api_server }/1.1${ url }`, {
          method,
          headers: {
            'X-LC-Id': this.app_id,
            'X-LC-Key': this.app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      this.addCount(Counter);
    },

    refreshCounter() {
      var api_server = this.app_id.slice(-9) !== '-MdYXbMMI' ? this.custom_api_server : `https://${ this.app_id.slice(0, 8).toLowerCase() }.api.lncldglobal.com`;
      if (api_server) {
        this.fetchData(api_server);
      } else {
        fetch('https://app-router.leancloud.cn/2/route?appId=' + this.app_id)
          .then(resp => resp.json())
          .then(({api_server}) => {
            this.fetchData('https://' + api_server);
          });
      }
    }

  };

  LCCounter.refreshCounter();

  document.addEventListener('pjax:complete', function () {
    LCCounter.refreshCounter();
  });
</script>








<script>
function listennSidebarTOC() {
  const navItems = document.querySelectorAll(".toc li");
  if (!navItems.length) return;
  const sections = [...navItems].map((element) => {
    const link = element.querySelector(".toc-link");
    const target = document.getElementById(
      decodeURI(link.getAttribute("href")).replace("#", "")
    );
    link.addEventListener("click", (event) => {
      event.preventDefault();
      window.scrollTo({
		top: target.offsetTop + 100,
		
		behavior: "smooth"
		
	  });
    });
    return target;
  });

  function activateNavByIndex(target) {
    if (target.classList.contains("active-current")) return;

    document.querySelectorAll(".toc .active").forEach((element) => {
      element.classList.remove("active", "active-current");
    });
    target.classList.add("active", "active-current");
    let parent = target.parentNode;
    while (!parent.matches(".toc")) {
      if (parent.matches("li")) parent.classList.add("active");
      parent = parent.parentNode;
    }
  }

  function findIndex(entries) {
    let index = 0;
    let entry = entries[index];
    if (entry.boundingClientRect.top > 0) {
      index = sections.indexOf(entry.target);
      return index === 0 ? 0 : index - 1;
    }
    for (; index < entries.length; index++) {
      if (entries[index].boundingClientRect.top <= 0) {
        entry = entries[index];
      } else {
        return sections.indexOf(entry.target);
      }
    }
    return sections.indexOf(entry.target);
  }

  function createIntersectionObserver(marginTop) {
    marginTop = Math.floor(marginTop + 10000);
    let intersectionObserver = new IntersectionObserver(
      (entries, observe) => {
        let scrollHeight = document.documentElement.scrollHeight + 100;
        if (scrollHeight > marginTop) {
          observe.disconnect();
          createIntersectionObserver(scrollHeight);
          return;
        }
        let index = findIndex(entries);
        activateNavByIndex(navItems[index]);
      },
      {
        rootMargin: marginTop + "px 0px -100% 0px",
        threshold: 0,
      }
    );
    sections.forEach((element) => {
      element && intersectionObserver.observe(element);
    });
  }
  createIntersectionObserver(document.documentElement.scrollHeight);
}

document.addEventListener("DOMContentLoaded", listennSidebarTOC);
document.addEventListener("pjax:success", listennSidebarTOC);
</script>

<!-- more -->

  


<script src="https://cdn.jsdelivr.net/npm/pjax@0.2.8/pjax.min.js"></script>


<script>
    var pjax;
    document.addEventListener('DOMContentLoaded', function () {
      pjax = new Pjax({
        elements: 'a[href]:not([href^="#"]):not([href="javascript:void(0)"]):not([pjax-fancybox])',
        selectors: [
          "title",
          "#l_cover",
          "#pjax-container",
          "#pjax-header-nav-list"
        ],
        cacheBust: false,   // url 地址追加时间戳，用以避免浏览器缓存
        timeout: 5000
      });
    });

    document.addEventListener('pjax:send', function (e) {
      //window.stop(); // 相当于点击了浏览器的停止按钮

      try {
        var currentUrl = window.location.pathname;
        var targetUrl = e.triggerElement.href;
        var banUrl = [""];
        if (banUrl[0] != "") {
          banUrl.forEach(item => {
            if(currentUrl.indexOf(item) != -1 || targetUrl.indexOf(item) != -1) {
              window.location.href = targetUrl;
            }
          });
        }
      } catch (error) {}

      window.subData = null; // 移除标题（用于一二级导航栏切换处）
      if (typeof $.fancybox != "undefined") {
        $.fancybox.close();    // 关闭弹窗
      }
      volantis.$switcher.removeClass('active'); // 关闭移动端激活的搜索框
      volantis.$header.removeClass('z_search-open'); // 关闭移动端激活的搜索框
      volantis.$wrapper.removeClass('sub'); // 跳转页面时关闭二级导航

      // 解绑事件 避免重复监听
      volantis.$topBtn.unbind('click');
      $('.menu a').unbind('click');
      $(window).unbind('resize');
      $(window).unbind('scroll');
      $(document).unbind('scroll');
      $(document).unbind('click');
      $('body').unbind('click');
	  
    });

    document.addEventListener('pjax:complete', function () {
      // 关于百度统计对 SPA 页面的处理：
      // 方案一：百度统计>管理>单页应用设置中，打开开启按钮即可对SPA进行统计。 https://tongji.baidu.com/web/help/article?id=324
      // 方案二：取消注释下列代码。 https://tongji.baidu.com/web/help/article?id=235
       

      // 关于谷歌统计对 SPA 页面的处理：
      // 当应用以动态方式加载内容并更新地址栏中的网址时，也应该更新通过 gtag.js 存储的网页网址。
      // https://developers.google.cn/analytics/devguides/collection/gtagjs/single-page-applications?hl=zh-cn
      


      $('.nav-main').find('.list-v').not('.menu-phone').removeAttr("style",""); // 移除小尾巴的移除
      $('.menu-phone.list-v').removeAttr("style",""); // 移除小尾巴的移除
      $('script[data-pjax], .pjax-reload script').each(function () {
        $(this).parent().append($(this).remove());
      });
      try{
          if (typeof $.fancybox == "undefined") {
            SCload_fancybox();
          } else {
            pjax_fancybox();
          }
        
		  Pjax_backstretch()
        
        
        
          pjax_scrollrebeal();
        
        if (typeof IssuesAPI == "undefined") {
          loadIssuesJS();
        }
        
          pjax_initCopyCode();
        
        
          pjax_valine();
        
        
        
        
        
        
      } catch (e) {
        console.log(e);
      }
	  
    });

    document.addEventListener('pjax:error', function (e) {
	  
      window.location.href = e.triggerElement.href;
    });
</script>
 
    </div>
  </body>
</html>
